package ht6_huffman;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * ArbolHuffman
 * @author Jorge Lainfiesta 11142
 * @since Sep 18, 2012
 * @version 1
 */
public class ArbolHuffman {
    
    private ArrayList<Caracter> alfabeto;
    private ArbolCaracter topArbol;
    private PriorityQueue<ArbolCaracter> carOrdenados;
    private int max_code_length = 0;
    
    /**
     * Constructor
     * Se forma el arbol al construirse el objeto
     * @param cadena 
     */
    public ArbolHuffman(String cadena){
        alfabeto = new ArrayList<Caracter>();
        generarAlfabeto(cadena);
        int sumcantidad = cadena.length();
        //Pasamos el alfabeto a la priority queue para ternelos ordenados
        carOrdenados =
                new PriorityQueue<ArbolCaracter>(10, 
                new FrecuencyComparator());
        
        for(Caracter car : alfabeto){
            ArbolCaracter arbol = new ArbolCaracter(car);
            carOrdenados.add(arbol);
        }
        while((carOrdenados.peek().getCantidad())<sumcantidad){
            //Obtenemos arboles hijos
            ArbolCaracter derecha = carOrdenados.poll();
            ArbolCaracter izquierda = carOrdenados.poll();
            
            //Hacemos contenido del nuevo padre
            Caracter actual = new Caracter(derecha.getCaracter()+izquierda.getCaracter());
            actual.setCantidad(derecha.getCantidad()+izquierda.getCantidad());
            ArbolCaracter nuevo = new ArbolCaracter(actual);
            nuevo.setLeft(izquierda);
            nuevo.setRight(derecha);
            
            //Los volvemos a agregar a la cola
            carOrdenados.add(nuevo);
        }
        ArbolIterator hojas = new ArbolIterator(carOrdenados.peek());
        
        while(!hojas.isEmpty()){
             ArbolCaracter hoja = hojas.next();
             ArbolCaracter padre = (ArbolCaracter) hoja.getParent();
             while(padre!=null){
                 hoja.pushDigit(padre.getCodigo());
                 padre = (ArbolCaracter) padre.getParent();
                 max_code_length++;
             }
        }
        
    }

    
    /**
     * Codifica un string en los códigos correspondientes
     * @param cadena
     * @return El string con los caracteres en sus códigos correspondientes
     * @throws Exception si hay una caracter que no es parte del alfabeto inicial
     */
    public String encode(String cadena) throws Exception{
        String[] chars = cadena.split("");
        String encoded = "";
        for(String c : chars){
            if(c.equals(""))
                 continue;
            int index = alfabeto.indexOf(new Caracter(c));
            if(index<0)
                throw new Exception("Caracter no válido: "+c);
            encoded+=alfabeto.get(index).getCodigo();
        }
        return encoded;
    }
    
    /**
     * Decodifica un código 
     * @param codigo
     * @return Sring de caracteres correspondiente
     * @throws Exception 
     */
    public String decode(String codigo) throws Exception{
        String decoded = "";
        int ini = 0;
        for(int i = 1; i<=codigo.length(); i++){
            for(int j = 0; j<alfabeto.size(); j++){
                if(codigo.substring(ini, i).equals(alfabeto.get(j).getCodigo())){
                    decoded+=alfabeto.get(j).getCaracter();
                    ini = i;
                    break;
                }
            }
            if(i-ini > max_code_length)
                throw new Exception("Código inválido");
        }
        return decoded;
    }
    
    /**
     * Retorna el alfabeto construido. Incluye caracter, código y frecuencia
     * @return 
     */
    public ArrayList<Caracter> getAlfabeto(){
        ArrayList<Caracter> alfa = (ArrayList<Caracter>) alfabeto.clone();
        Collections.sort(alfa, new CFrecuencyComparator());
        return alfa;
    }
    
    /**
     * Genera el alfabeto a partir de la cadena
     * @param cadena 
     */
    private void generarAlfabeto(String cadena){
        //Agregaremos los caracteres
        String[] chars = cadena.split("");
        for(String c : chars){
            if(c.equals(""))
                 continue;
            Caracter carac = new Caracter(c);
            if(alfabeto.contains(carac)){
                //Si existía, aumentar cantidad
                alfabeto.get(alfabeto.indexOf(carac)).aumentarCantidad();
            }else{
                //Si no, agregarlo
                alfabeto.add(carac);
            }
        }
    }

}
